function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 选择排序 我的实现
function selectionSort(arr) {
    for (let i = 0, len = arr.length; i < len ;++i) {
        let minIndex = i
        let variable = arr[minIndex]
        for (let j = i + 1; j < arr.length; ++j) {
            if (arr[minIndex] > arr[j]) {
                variable = arr[j]
                arr[j] = arr[minIndex]
                arr[minIndex] = variable
            }
        }
    }
}

// 老师的方法
function selectionSort2(arr) {
    const len = arr.length
    for (let i = 0; i < len;++i) {
        // 寻找[ i, len)中最小值
        let minIndex = i
        for(let j = i +1; j<len; ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }
        let variable = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = variable
    }
}

let a = [1,5,8,7,4,6,9,8,2,1]
selectionSort2(a)
console.log(a)

// 插入排序
function insertSort(arr) {
    for (let i = 1, len = arr.length; i < len; i++) {
        for (let j = i; j > 0; j--) {
            if (arr[j] < arr[j -1]) {
                let variable = arr[j]
                arr[j] = arr[j-1]
                arr[j-1] = variable
            } else {
                break
            }
        }
    }
}

// 选择排序最优解
function insertSort2 (arr) {
    for (let i = 1; i < arr.length; i++) {
        let variable = arr[i], j; // j是保存插入的位置
        for (j = i; j > 0; j--) {
            if(variable < arr[j-1]) {
                arr[j] = arr[j-1]
            } else {
                break
            }
        }
        arr[j] = variable
    }
}

let b = [1,5,8,7,4,6,9,8,2,1]
insertSort2(b)
console.log(b)

// 冒泡排序
function bubbleSort (arr) {
    /*for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - 1 - i; j++) {  // 把最大值放在最后面
            if (arr[j] > arr[j +1]) {
                swap(arr, j , j + 1)
            }
        }
    }*/
    for (let i = arr.length; i > 0 ; i--) {
        for (let j = i; j > 0; j--) {
            if (arr[j] > arr[j+1]) {
                swap(arr, j, j +1)
            }
        }
    }
}

/* 选择排序指交换两个元素时并不影响其他元素的相邻位置，
而冒泡排序在交换过程中会改变其他元素的相邻位置,选择排序是与输入无关的，
每次选择都要遍历待排序序列，时间复杂度固定约为N^2/2，而冒泡排序与输入有关，如果一轮遍历没有元素交换，
就可以断定序列已经有序，其时间复杂度平最好时可以达到N，最坏约N^2/2，平均时间复杂度虽然增长量级也是N^2/2，
但实际是要优于选择排序的，具体取决于待排序序列的部分有序程度 */

let c = [1,5,8,7,4,6,9,8,2,1]
bubbleSort(c)
console.log(c)